Integrated Circuits are the basic parts of most electronic systems such as computers, digital cameras, wireless communication systems, Internet devices, networking devices and systems, automotive electronic systems, control systems, and power electronics. An IC is an interconnected array of active and passive elements integrated with a single semiconductor substrate or deposited on the substrate by a continuous series of compatible processes, and capable of performing at least one complete electronic circuit function. ICs are usually hosted on a printed circuit board (PCB). A PCB is a flat board whose front contains slots for integrated circuit chips and connections for a variety of electronic components, and whose back is printed with electrically conductive pathways between the components.
With the rapid advance of current semiconductor technology, the size of the ICs has been very much reduced while the speed of the ICs has greatly increased. This leads to much higher data transmission rates, diminishing size of the electronic devices, and increase functionalities of the electronic products. These make the design of the electronic devices more difficult and increase the challenges in the analysis of power and signal integrity problem. Designers of electronic systems are increasingly dependent on software tools that can effectively overcome these technique difficulties. However, conventional signal-integrity analysis tools are circuit-based and lack the accuracy required for high-speed integrated circuit design. Wave solutions based on the Maxwell's equations are essential for the advanced analysis of printed circuit boards (PCBs), IC components, and packages, to address the rigorous demands of circuit design.
Electromagnetic problems are governed by Maxwell's equations, which can be formulated into the surface integral equations using a Green's function. Using the method of moments (MoM), the integral equation can be cast into the matrix equation. In a matrix equation, the product of the impedance matrix and an unknown column vector is equal to a given column vector. The given column vector corresponds to the given incident wave. The unknown column vector corresponds to the unknown induced current and charges. The objective is to solve for the unknown column vector. The Green's function integral equation approach has the advantage that it takes into account the propagation of waves from one point to another. It also has the advantage, for numerical solutions of the surface integral equation, that only surface unknowns are required on the object surface. However, using Greens function leads to matrix equations with a full impedance matrix, which relates the source locations to the observation points through propagation. If there are N surface unknowns in the matrix equation, a traditional technique for solving the column vector of matrix equations, such as the matrix inversion method, Gaussian elimination method or the LU decomposition method, takes O(N3) computational steps and O(N2) of memory. Thus, the computation becomes resource intensive when N is large. For example, at present, using a single processor of 2.66 GHz, it requires CPU 15 minutes and Memory of 235 Mb to solve the case of N=5000. Assuming the scaling with N given above, for N=65000, the technique of matrix inversion will require 550 hours CPU and 39,715 Mb memory on a single processor. This is impossible for a single PC processor today. Thus matrix inversion cannot be used for such problems of large dense matrix.
Thus for such problems, a common methodology is to use an iterative method of solutions of the matrix equation. The iteration method means that we start with an initial guess of the column vector. In each iteration, the column vector for the matrix equation is solved by iteration of the previous column vector. Each iteration requires the product of the impedance matrix with the column vector of the previous step. This process continues until the column vector converges. Using the iterative approach, the total CPU will be the pre-processing time plus the number of iterations times the CPU for each iteration. Thus the bottleneck of the method is the calculation of the product of the impedance matrix and a column vector in each iteration step . The column vector is the solution in the previous iteration. In this case, the computational steps are still O(N2) per iteration and memory requirements are still O(N2), so these standard techniques of solving Maxwell's solvers will have large memory and CPU requirements.
For these reasons, for complicated simulation problems with many unknowns, present day electronic design automation (EDA) solvers may take days or even weeks to complete the solution of a single instance of Maxwell's equation. The advanced EDA software tools required for the high-speed circuit design have to be both memory and CPU efficient while without sacrificing the accuracy of the solutions. The EDA software tools with such performance are critical to ensure high performance and reduce time for the designed electronic products to market. It will provide a distinct competitive advantage for the circuit designers who use them because the solutions permit them to more efficiently design and evaluate their products and systems.
In recent years, two techniques have become popular to accelerate impedance matrix-column vector computation. The techniques also save on computer memory. The methods are the sparse matrix canonical grid method (SMCG) and the multi-level fast multipole method (MLFMM). Both methods have been used for large-scale 3D simulations.
The SMCG exhibits computational complexity of O(N log N) per iteration and memory requirement of O(N). It operates by expanding the Green's function as a Taylor series on a canonical grid. The surface fields on the transmitted elements are first projected onto the canonical grid and then the interactions on the canonical grids are calculated simultaneously with the fast Fourier transform (FFT). The receiving fields on the canonical grids are then projected back to the scattering elements. An advantage of the SMCG method is that it only requires a translationally invariant Green's function and can be readily applied with the multi-layered medium Green's function. The SMCG method is FFT based, so that parallel implementation can be accomplished by using a parallel version of FFT.
The MLFMM method exhibits computational complexity of O(N log N) per iteration and so does memory requirements. The idea of the FMM is that instead of calculating interactions of two non-near groups directly, the transmitting field of each scattering element in the group is projected onto the group center and then only interactions between two centers are computed. The receiving field at each group center is then projected back to the scattering elements in the group. As the group becomes bigger, FMM uses interpolation and anterpolation (decimation) techniques to compute the scattering from one level of groups to the next level of groups.
The advantage of the SMCG is that it is efficient for densely packed scattering elements when the scattering elements can be translated easily to the canonical grid. It is not efficient for the sparse distributed scattering objects. This is because there are no scattering objects around some of canonical grids and we still have to include them in the calculations. The FMM, on the other hand, relies on diagonalization of the T matrix using plane waves. It is difficult to use with a multi-layered medium Green's function. Its reliance on interpolation and anterpolation also makes it difficult to parallelize efficiently. Also the method is inefficient at low and intermediate frequencies which are common for RF circuit problems because of the large number of multipoles still required for such problems.
It would therefore be desirable to develop a fast surface integral equation solver which has advantages over both the SMCG and the FMM for certain classes of problems. Such a solver should preferably apply to any Green's function, such as a multi-layered medium Green's function, and also sparsely packaged structures while keep the efficiency of matrix-vector multiplication and less memory requirements. The solver should also preferably be easy to parallelize. The solver should desirably work from low to high frequencies.